public class SinglyList<T> extends Object {
    /***
     * 3.返回单链表中和元素x相等的序号，不存在该元素返回-1值。 4.单链表就地逆置。
     * 5.la，lb为两个带头结点的单链表的头指针，从la中删除自第i个元素起共len个元素后，将他们插入表lb的第j个元素前。
     ***/

    // 构造头指针
    public Node<T> head;
    // 构造尾指针
    private Node<T> last;
    // 链表长度
    private int length = 0;

    // 创建头结点与修正尾指针
    public SinglyList() {
        // 创建头结点
        this.head = new Node<T>();
        // 初始状态下头结点与尾指针浅拷贝对齐
        this.last = this.head;
    }

    public SinglyList(T[] values) {

        // 创建头结点与尾指针
        this();
        // 数据倒入操作（直接使用尾指针实现）
        for (int i = 0; i < values.length; i++) {
            last.next = new Node<T>(values[i], null);
            last = last.next;
        }
    }

    // 结点插入操作，使用自适应优化
    public Node<T> insert(int i, T x) {
        Node<T> front = this.head;
        // 寻找最后一个结点或插入结点
        for (int j = 0; front.next != null && j < i - 1; j++) {
            front = front.next;
        }
        front.next = new Node<T>(x, front.next);
        if (i == this.length) {
            last = last.next;
        }
        this.length++;
        return front.next;
    }

    // 快速插入
    public Node<T> insert(T i) {
        last.next = new Node<T>(i, null);
        last = last.next;
        this.length++;
        return last;
    }

    public boolean insertNode(int i,Node<T> p) {
        if( i > this.length && i < 0){
            return false;
        }else{
            Node<T> front = this.head;
            for (int j = 0; j < i; j++) {
                front = front.next;
            }
            Node<T> next = front.next;
            front.next = p;
            while (p.next != null) {
                p = p.next;
                this.length++;
            }
            length++;
            p.next = next;
            return true;
        }
    }

    public Node<T> remove(int i, int len) {
        Node<T> front = this.head;
        if (i > this.length) {
            return null;
        } else {
            for (int j = 1; j < i; j++) {
                front = front.next;
            }
            Node<T> next = front.next;
            for (int j = 1; j < len; j++) {
                next = next.next;
            }
            Node<T> p = front.next;
            front.next = next.next;
            this.length = this.length - len;
            next.next = null;
            return p;
        }
    }

    // 获取第i个元素的元素值
    public T get(int i) {
        Node<T> p = this.head;
        for (int j = 0; j < i && p != null; j++) {
            p = p.next;
        }
        return p.data;
    }

    // 打印链表
    public void print() {
        Node<T> p = this.head;
        for (int i = 0; i < this.length; i++) {
            p = p.next;
            System.out.print(p.data + "\t");
        }
        System.out.println();
    }

    // 3.返回单链表中和元素x相等的序号，不存在该元素返回-1值。
    public int getLocation(T x) {
        Node<T> p = this.head.next;
        int j = -1, i = 1;
        while (p != null) {
            if (p.data == x) {
                j = i;
                break;
            }
            p = p.next;
            i++;
        }
        return j;
    }

    // 单链表就地逆置（原理，从第二个元素开始遍历，依次放到头结点后面）
    public boolean reverseOrder() {
        // 判断表是否需要逆置
        if (this.length <= 1) {
            return false;
        } else {
            // 保存第二个结点
            Node<T> p = this.head.next.next;
            // 清空首元结点的指针域
            this.head.next.next = null;
            // 调整尾指针
            this.last = this.head.next;
            Node<T> q;
            while (p != null) {
                // 防止进入断链死循环
                q = p.next;
                // 将第二个结点的指针域指向第一个结点（会断链）
                p.next = this.head.next;
                // 将第一个结点替换为第二个结点
                this.head.next = p;
                // 断链接回
                p = q;
            }
            return true;
        }

    }

    // 调试用（查询指针）
    public void printL() {
        Node<T> p = this.head;
        for (int i = 0; i < this.length; i++) {
            p = p.next;
            System.out.print("(" + p + "," + p.next + ")" + "\t");
        }
        System.out.println();
    }
}